package 二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class 通用框架 {

    public Stack<TreeNode> stack = new Stack<>();

    // 将左侧树枝全部入栈
    public void pushLeft(TreeNode p, List<Integer> ans) {
        while (p != null) {
            // todo ans.add(p.val);
            stack.push(p);
            p = p.left;
        }
    }

    public List<Integer> traverse(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode visited = new TreeNode(-1);
        pushLeft(root, ans);
        while (!stack.isEmpty()) {
            TreeNode p = stack.peek();

            // 中序遍历的进入条件：某个节点左边全部遍历完毕，但是右边没有遍历
            if ((p.left == null || p.left == visited) && p.right != visited) {
                // todo ans.add(p.val);

                pushLeft(p.right, ans);  // 从p的右子树开始作为
            }

            // 后序遍历进入的条件：某个节点再也没有右子树了
            if (p.right == null || p.right == visited) {
                // todo ans.add(p.val);

                visited = stack.pop(); // 以p为根的子树遍历完毕，出栈
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);

        t1.left = t2;
        t1.right = t5;
        t2.left = t3;
        t2.right = t4;
        t5.right = t6;

        通用框架 obj = new 通用框架();
        List<Integer> ans = obj.traverse(t1);
        System.out.println(Arrays.toString(ans.toArray()));
    }
}
